#include "stdafx.h"

#include "dp_trie_cidr.h"
#include "dp_trie_value.h"

#include "dp_trie_string2.h"

namespace dp {
dp_trie_string2_node::dp_trie_string2_node(
    char c, std::shared_ptr<dp_trie_string2_node>& parent)
    : parent_(parent), rule_obj_(NULL), bend_(false), c_(c) {}

dp_trie_string2_node::~dp_trie_string2_node() {}

void dp_trie_string2_node::get_tree_str(std::string& str) {
    if (0 != c_) {
        str.insert(0, 1, c_);
    }
    if (parent_) {
        parent_->get_tree_str(str);
    }
}

dp_trie_string2::dp_trie_string2() {
    std::shared_ptr<dp_trie_string2_node> n;
    root_ = std::make_shared<dp_trie_string2_node>(0, n);
}

dp_trie_string2::~dp_trie_string2() {}

bool dp_trie_string2::insert(const std::string& rule,
                             std::shared_ptr<dp_trie_cidr>& rule_obj) {
    if (rule.empty()) {  // 忽略空规则
        return false;
    }
    rules_.push_back(rule);
    auto node = root_;
    for (size_t i = 0; i != rule.size(); i++) {
        char c = rule[i];
        if (!node->child_.count(c)) {
            node->child_[c] = std::make_shared<dp_trie_string2_node>(c, node);
        }
        node = node->child_[c];
    }
    node->bend_ = true;
    node->rule_obj_ = rule_obj;
    node->set_rule(rule);
    return true;
}

bool dp_trie_string2::search(std::shared_ptr<dp_trie_value>& value,
                             std::stack<std::string>& params) {
    if (params.empty()) {
        return false;
    }
    std::string dn = params.top();
    params.pop();
    return search(value, dn, params, NULL);
}

bool dp_trie_string2::search(std::shared_ptr<dp_trie_value>& value,
                             const std::string& str,
                             std::stack<std::string>& params,
                             std::string* dn_rule) {
    if (str.empty()) {
        return false;
    }
    return match(value, root_, str.c_str(), params, dn_rule);
}

bool dp_trie_string2::match(std::shared_ptr<dp_trie_value>& value,
                            std::shared_ptr<dp_trie_string2_node>& node_s,
                            const std::string& dn,
                            std::stack<std::string>& params,
                            std::string* dn_rule) {
    const char* domain = dn.c_str();
    if (NULL == domain || 0 == *domain || NULL == node_s) {
        return false;
    }
    int dn_pos = 0;
    int dn_len = strlen(domain);
    auto node = node_s;
    do {
        char c = domain[dn_pos];
        if (node->child_.find(c) != node->child_.end()) {
            node = node->child_[c];
            dn_pos++;
        } else if (node->child_.find('?') != node->child_.end()) {
            node = node->child_['?'];
            dn_pos++;
        } else if (node->child_.find('*') != node->child_.end()) {
            node = node->child_['*'];
            // 继续往下匹配，直到找到规则的结尾
            if (fuzzy_match(value, node, domain + dn_pos, params, dn_rule)) {
                return true;
            }
            break;
        } else {
            // 查找上一级的是否存在*或?
            int tmp_deep = dn_pos - 1;
            auto node_p = node->parent_;
            while (tmp_deep >= 0 && node_p) {
                std::shared_ptr<dp_trie_string2_node> tmp_node;
                if (node_p->child_.find('*') != node_p->child_.end()) {
                    tmp_node = node_p->child_['*'];
                } else if (node_p->child_.find('?') != node_p->child_.end()) {
                    tmp_node = node_p->child_['?'];
                }
                if (tmp_node && fuzzy_match(value, tmp_node, domain + tmp_deep,
                                            params, dn_rule)) {
                    return true;
                }
                tmp_deep--;
                node_p = node_p->parent_;
            }
            return false;  // 没有匹配的路径
        }
    } while (dn_pos < dn_len);

    bool bret = false;
    // 检查最终节点是否是一个规则的结尾
    if (node && node->bend_ && node->rule_obj_) {
        if (dn_rule && dn_rule->empty()) {
            *dn_rule = node->get_rule();
        }
        value = node->rule_obj_;
        bret = node->rule_obj_->search(value, params);
    }
    return bret;
}

bool dp_trie_string2::fuzzy_match(std::shared_ptr<dp_trie_value>& value,
                                  std::shared_ptr<dp_trie_string2_node>& node,
                                  const char* domain,
                                  std::stack<std::string>& params,
                                  std::string* dn_rule) {
    if (NULL == node || node->bend_) {
        return false;
    }
    for (auto it = node->child_.begin(); it != node->child_.end(); ++it) {
        const char* tmp_pos = strchr(domain, it->first);
        while (tmp_pos) {
            if (match(value, it->second, tmp_pos + 1, params, dn_rule)) {
                return true;
            }
            tmp_pos = strchr(tmp_pos + 1, it->first);
        }
    }
    return false;
}

void dp_trie_string2::printf_root() {
    auto node = root_;
    std::string tmp;
    for (auto& pair : node->child_) {
        tmp.push_back(pair.first);
        tmp.append(" ");
    }
    for (size_t i = 0; i < rules_.size(); ++i) {
        printf("rule%zd:%s\n", i, rules_[i].c_str());
    }
    printf("root child is:%s\n", tmp.c_str());
}

}  // namespace dp
